//! 有向无环图构建与拓扑排序模块
//!
//! 该模块负责基于表达式依赖自动构建有向无环图，进行拓扑排序和循环检测

use anyhow::anyhow;
use petgraph::algo::toposort;
use petgraph::graph::{DiGraph, NodeIndex};
use std::collections::HashMap;

/// 有向无环图结构
pub struct Dag {
    /// 图结构
    graph: DiGraph<String, ()>,
    /// 节点索引映射
    node_indices: HashMap<String, NodeIndex>,
}

impl Dag {
    /// 创建新的DAG实例
    pub fn new() -> Self {
        Self {
            graph: DiGraph::new(),
            node_indices: HashMap::new(),
        }
    }
    
    /// 添加节点
    pub fn add_node(&mut self, name: &str) -> NodeIndex {
        if let Some(index) = self.node_indices.get(name) {
            *index
        } else {
            let index = self.graph.add_node(name.to_string());
            self.node_indices.insert(name.to_string(), index);
            index
        }
    }
    
    /// 添加边
    pub fn add_edge(&mut self, from: &str, to: &str) {
        let from_index = self.add_node(from);
        let to_index = self.add_node(to);
        self.graph.add_edge(from_index, to_index, ());
    }
    
    /// 获取拓扑排序
    pub fn topological_sort(&self) -> Result<Vec<String>, anyhow::Error> {
        match toposort(&self.graph, None) {
            Ok(order) => {
                Ok(order.iter().map(|i| self.graph[*i].clone()).collect())
            },
            Err(_) => Err(anyhow!("Cycle detected in DAG"))
        }
    }
    
    /// 检测是否存在循环
    pub fn has_cycle(&self) -> bool {
        toposort(&self.graph, None).is_err()
    }
}